{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "5433fae2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "arr = [1,3,4,4,1,2,7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "f4b8d1a2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 4, 4, 7]\n"
     ]
    }
   ],
   "source": [
    "## 冒泡排序\n",
    "# 原地排序，平均时间复杂度：O(n^2)\n",
    "def bubbleSort(arr: List):\n",
    "    n = len(arr)\n",
    "    for i in range(1,n):\n",
    "        flag = False\n",
    "        for j in range(0,n-i):\n",
    "            if arr[j]>arr[j+1]:\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "                flag = True\n",
    "        if not flag: break\n",
    "    print(arr)\n",
    "\n",
    "arr1 = deepcopy(arr)\n",
    "bubbleSort(arr1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "657bbde7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 4, 4, 7]\n"
     ]
    }
   ],
   "source": [
    "## 插入排序\n",
    "# 原地排序， 平均时间复杂度：O(n^2)\n",
    "# 有序区，无序区\n",
    "def insertionSort(arr: List): \n",
    "    n = len(arr)\n",
    "    for i in range(1,n):\n",
    "        value = arr[i]\n",
    "        pointer = i-1\n",
    "        while pointer>=0 and arr[pointer]>value:  # 大于目标值的整体右移\n",
    "            arr[pointer+1] = arr[pointer] \n",
    "            pointer -= 1\n",
    "        arr[pointer+1] = value # 插入\n",
    "    print(arr)\n",
    "\n",
    "arr1 = deepcopy(arr)\n",
    "insertionSort(arr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "8a54c426",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 4, 4, 7]\n"
     ]
    }
   ],
   "source": [
    "## 选择排序\n",
    "# 原地排序，平均时间复杂度：O(n^2)\n",
    "# 有序区，无序区\n",
    "# 从无序区中挑选最小值，放在有序区的末尾\n",
    "\n",
    "def selectionSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n-1):\n",
    "        minPos = i\n",
    "        for j in range(i,n):\n",
    "            if arr[minPos]>arr[j]: minPos = j\n",
    "        arr[i],arr[minPos] = arr[minPos], arr[i]\n",
    "    print(arr)\n",
    "\n",
    "arr1 = deepcopy(arr)\n",
    "selectionSort(arr1)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "74792cb4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 3, 4, 4, 7]\n"
     ]
    }
   ],
   "source": [
    "## 希尔排序---插入排序的进阶版\n",
    "# 原地排序， 平均时间复杂度：O(n^2)\n",
    "# 有序区，无序区\n",
    "# 把间隔从大到小\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "\n",
    "def shellSort(arr: List):\n",
    "    n = len(arr)\n",
    "    incr = n//2\n",
    "    while incr > 0:\n",
    "        for i in range(incr,n, incr):\n",
    "            value = arr[i]\n",
    "            pointer = i - incr\n",
    "            while pointer>=0 and arr[pointer]>value:\n",
    "                arr[pointer+incr] = arr[pointer]\n",
    "                pointer -= incr\n",
    "            arr[pointer+incr] = value\n",
    "        incr //= 2\n",
    "    print(arr)\n",
    "    \n",
    "arr1 = deepcopy(arr)\n",
    "shellSort(arr1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01990a98",
   "metadata": {},
   "source": [
    "## 归并排序\n",
    "将数组分割为两份，分别排序后，再进行有序合并\n",
    "使用递归的方法，可以把数组继续分割，直到每份只包含一个元素，然后递归的向上有序合并"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "36018f5d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 4, 4, 7]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 归并排序\n",
    "# 非原地排序，平均时间复杂度: O(nlogn)\n",
    "# 在原数组上进行操作\n",
    "\n",
    "def mergeSort(num:list, left:int, right:int)->None:\n",
    "\n",
    "    def merge(num:list, left:int, mid:int, right:int)->None:\n",
    "        arr1, arr2 = [],[]\n",
    "        for i in range(left, mid+1):  # 左侧包含中间值\n",
    "            arr1.append(num[i])\n",
    "        arr1.append(float('inf'))\n",
    "\n",
    "        for i in range(mid+1,right+1): # 右侧不包含中间值\n",
    "            arr2.append(num[i])\n",
    "        arr2.append(float('inf'))\n",
    "\n",
    "        i1=i2=0\n",
    "        for i in range(left,right+1):\n",
    "            if arr1[i1]<arr2[i2]:\n",
    "                num[i]=arr1[i1]\n",
    "                i1+=1\n",
    "            else:\n",
    "                num[i]=arr2[i2]\n",
    "                i2+=1\n",
    "\n",
    "    if left>=right:\n",
    "        return\n",
    "\n",
    "    mid = left + (right-left)//2\n",
    "    mergeSort(num,left,mid)\n",
    "    mergeSort(num,mid+1,right)\n",
    "    merge(num,left,mid,right)\n",
    "\n",
    "\n",
    "\n",
    "num1 = deepcopy(arr)\n",
    "mergeSort(num1,0,len(num1)-1)\n",
    "num1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3731dbe",
   "metadata": {},
   "source": [
    "## 快速排序\n",
    "\n",
    "特点： **原地排序**， 平均时间复杂度：**O(nlogn)**; 最坏时间复杂度：$ O(n^2) $\n",
    "\n",
    "1. 为数组选定一个基准值，这里采用的是最后一个值（使用哪一个都可以）\n",
    "2. 使用快慢指针的方法，找到基准值的位置：该位置左侧所有数值都小于基准值，右侧所有值都大于基准值\n",
    "3. 使用基准值把原数组分割为两个数组，对每个数组调用 （1），（2）两步处理，直到分割后的数组只包含一个值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "b43a7b99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 4, 4, 7]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "## 快速排序\n",
    "# 原地排序，平均时间复杂度：O(nlogn)\n",
    "def quickSort(num:list, left:int, right:int)->None:\n",
    "    \n",
    "    # 寻找基准值应该在的位置\n",
    "    def partition(num:list, left:int, right:int)->int:\n",
    "        pos, val = left, num[right] # 取数组最后一个元素作为基准值\n",
    "        for i in range(left, right):\n",
    "            if num[i]<val:  # 将小于基准值的元素从左向右排，并使用慢指针记录当前排序的末尾位置\n",
    "                num[pos],num[i] = num[i],num[pos]\n",
    "                pos += 1\n",
    "        num[pos],num[right] = num[right],num[pos] # 将基准值放置到应该在的位置\n",
    "        return pos # 返回基准值位置\n",
    "    \n",
    "    if left>right:\n",
    "        return\n",
    "    \n",
    "    pos = partition(num, left, right)\n",
    "    quickSort(num, left, pos-1)\n",
    "    quickSort(num, pos+1, right)\n",
    "    \n",
    "\n",
    "\n",
    "arr1 = deepcopy(arr)\n",
    "quickSort(arr1,0,len(arr1)-1) \n",
    "arr1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "121c7491",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 4, 4, 7]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    " \n",
    "## 快速排序 V2\n",
    "# 随机选择基准点，交换到首位\n",
    "# 左右双指针，双向奔赴，小于pivot的放在前面，大于pivot的放在后面，直到两个指针相遇\n",
    "\n",
    "def fast_sortV2(arr: List, left: int, right: int):\n",
    "    if left>=right:\n",
    "        return\n",
    "    pos = partitionV2(arr, left, right)\n",
    "    fast_sortV2(arr,left,pos-1)\n",
    "    fast_sortV2(arr,pos+1,right)\n",
    "    \n",
    "import random\n",
    "def partitionV2(arr: List, left: int, right: int):\n",
    "    pos = random.randint(left, right)\n",
    "    arr[pos],arr[left] = arr[left], arr[pos]\n",
    "    pivot = arr[left]\n",
    "    leftP,rightP = left, right\n",
    "    while leftP<rightP:\n",
    "        # 从右向左找第一个小于pivot的值\n",
    "        while leftP<rightP and arr[rightP]>=pivot: rightP -= 1\n",
    "        arr[leftP] = arr[rightP]\n",
    "        # 从左向右找第一个大于pivot的值\n",
    "        while leftP<rightP and arr[leftP]<=pivot: leftP += 1\n",
    "        arr[rightP] = arr[leftP]\n",
    "    arr[leftP] = pivot\n",
    "    return leftP\n",
    "\n",
    "\n",
    "arr1 = deepcopy(arr)\n",
    "fast_sortV2(arr1,0,len(arr1)-1)\n",
    "arr1"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.12 ('base')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.8"
  },
  "vscode": {
   "interpreter": {
    "hash": "d2096cae6659ee4fb1716e8c5d85c87d2eefb77cfa807d438df8471a89810997"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
